home *** CD-ROM | disk | FTP | other *** search
/ BBS in a Box 3 / BBS in a box - Trilogy III.iso / Files / Prog / U-Z / VideoToolBox Folder / VideoToolboxSources / randU.c < prev    next >
Encoding:
C/C++ Source or Header  |  1993-02-23  |  4.9 KB  |  139 lines  |  [TEXT/KAHL]
  1. /*
  2. randU.c
  3. Denis G. Pelli
  4.  
  5. i=randU();
  6. randU() is the ANSI standard random number generator rand()—see K&R—
  7. modified to return 16 bits as an unsigned short int instead of just 15 bits
  8. as a (positive) short int. Both versions satisfy Knuth's prescriptions for a linear
  9. congruential random number generator, namely, given that the modulus is
  10. 2^32, the multiplier should be between 0.01m and 0.99m, the multiplier mod 8 should
  11. be 5, and the addend should be odd. (Knuth also recommends
  12. doing spectral testing of the multiplier, and I don't know if that's been
  13. done. One would like to think that the ANSI C committee would have chosen
  14. a multiplier that had been so tested.)
  15.  
  16. j=randUL();
  17. randUL() returns a 32-bit random number, formed by calling randU() twice and
  18. gluing the results together.
  19.  
  20. RandFill(address,bytes);
  21. is a tight coding of randU() optimized for filling large buffers. It
  22. is numerically equivalent, and even uses the same seed.
  23.  
  24. Kernighan, B. W. and Ritchie, D. M. (1988) The C Programming Language, Second Ed.
  25. Englewood Cliffs, NJ: Prentice Hall, p. 46.
  26.  
  27. Knuth, D. E. (1981) The Art of Computer Programming: 2. Seminumerical Algorithms, 
  28. Second Edition.  Reading, MA: Addison Wesley. pp. 170-171.
  29.  
  30. HISTORY:
  31. 8/4/89    dgp    wrote it.
  32. 3/19/90    dgp    eliminated assembly code to make it portable. This required defining a
  33.             union. I don't know how to initialize a static union, so I left it
  34.             uninitialized.
  35. 8/5/91    dgp    added RandFill(). Calling RandFill() to fill a buffer
  36.             will have exactly the same result as repeatedly calling randU(), 
  37.             two bytes at a time, but takes
  38.             about half the time. randU's seed is updated to reflect the activity.
  39.             RandFill() runs at about 1.2 µs/byte on a Mac IIci.
  40. 8/24/91    dgp    Made compatible with THINK C 5.0.
  41. 10/21/91 dgp Removed obsolete inclusion of MacProto.h.
  42. 9/13/92    dgp    Added randUL().
  43. */
  44. #include "VideoToolbox.h"
  45.  
  46. typedef union {
  47.     unsigned long L;
  48.     struct {
  49.         short high;
  50.         short low;
  51.     } S;
  52. } seedType;
  53.  
  54. static seedType seed={314159265};
  55.  
  56. unsigned short randU(void)
  57. {
  58.     seed.L = seed.L * 1103515245L + 12345L;
  59.     return seed.S.high;
  60. }
  61.  
  62. #if USHRT_MAX!=0xffff || ULONG_MAX!=0xffffffff
  63.     #error "randUL() assumes 16 bit unsigned short and 32 bit unsigned long"
  64. #endif
  65.  
  66. unsigned long randUL(void)
  67. {
  68.     return ((unsigned long)randU()<<16)+randU();
  69. }
  70.  
  71. /*    srandU - seed pseudo-random number generator    */
  72.  
  73. void srandU(unsigned n)
  74. {
  75.     seed.L = n;
  76. }
  77.  
  78. /*
  79. RandFill uses exactly the same algorithm as randU, using the same seed,
  80. but is coded to fill a large buffer quickly.
  81.  
  82. The trick here is to avoid having to do a bit shift to get at the high word of
  83. the s register. I do this by moving the entire long register to memory, overwriting
  84. the least significant two bytes on the next iteration. As a result this method
  85. requires a 2 byte overhang beyond the end of the desired data. That overhang region
  86. and an odd byte, if any, is filled in by copying from a workArea.
  87.  
  88. A simpler way to implement this overhang business would have been to copy the
  89. memory that was to be overwritten, overfill the buffer, and then restore the
  90. overwritten memory. The problem with that method is that it assumes the overwritten
  91. memory exists (e.g. it might be video memory) and won't be used while we're running, 
  92. which is not an entirely safe assumption unless we turn off interrupts. So I took 
  93. the cautious approach, which makes for
  94. a messier looking program, but it's safe. The performance cost is negligible.
  95. */
  96. void RandFill(void *address,long bytes)
  97. {
  98.     register long i;
  99.     register unsigned long s,mul,add;
  100.     register unsigned short *ptr;
  101.     unsigned short *savePtr,workArea[3];
  102.  
  103.     s=seed.L;
  104.     mul=1103515245L;
  105.     add=12345L;
  106.     ptr=(unsigned short *)address;
  107.     i=bytes;
  108.     i-=2;                    /* allow guard room for overshoot */
  109.     /* Because of the unrolling, the loop overhead is only 3% of running time */
  110.     for(;i>=32;i-=32) {
  111.         /* this compiles to 4 instructions: MULU.L, ADD.L, MOVE.L, ADDQ.L */
  112.         s *= mul; s += add; *(unsigned long *)ptr=s; ptr++;
  113.         s *= mul; s += add; *(unsigned long *)ptr=s; ptr++;
  114.         s *= mul; s += add; *(unsigned long *)ptr=s; ptr++;
  115.         s *= mul; s += add; *(unsigned long *)ptr=s; ptr++;
  116.         s *= mul; s += add; *(unsigned long *)ptr=s; ptr++;
  117.         s *= mul; s += add; *(unsigned long *)ptr=s; ptr++;
  118.         s *= mul; s += add; *(unsigned long *)ptr=s; ptr++;
  119.         s *= mul; s += add; *(unsigned long *)ptr=s; ptr++;
  120.         s *= mul; s += add; *(unsigned long *)ptr=s; ptr++;
  121.         s *= mul; s += add; *(unsigned long *)ptr=s; ptr++;
  122.         s *= mul; s += add; *(unsigned long *)ptr=s; ptr++;
  123.         s *= mul; s += add; *(unsigned long *)ptr=s; ptr++;
  124.         s *= mul; s += add; *(unsigned long *)ptr=s; ptr++;
  125.         s *= mul; s += add; *(unsigned long *)ptr=s; ptr++;
  126.         s *= mul; s += add; *(unsigned long *)ptr=s; ptr++;
  127.         s *= mul; s += add; *(unsigned long *)ptr=s; ptr++;
  128.     }
  129.     for(;i>=2;i-=2) {
  130.         s *= mul; s += add; *(unsigned long *)ptr=s; ptr++;
  131.     }
  132.     i+=2;                    /* remove guard */
  133.     savePtr=ptr;
  134.     ptr=&workArea[0];
  135.     s *= mul; s += add; *(unsigned long *)ptr=s; ptr++;
  136.     s *= mul; s += add; *(unsigned long *)ptr=s; ptr++;
  137.     memcpy((void *)savePtr,(void *)workArea,i);
  138.     seed.L=s;
  139. }